package com.rui.shangXueTang.sort;

import java.util.Arrays;

/**
 * @author : [锐神NO.3]
 * @version : [v1.0]
 * @className : BasicSort
 * @createTime : [2022/2/15 22:43]
 * @description : [基数排序]
 */

public class BasicSort {
    public static void main(String[] args) {

        int[] arrays = {53,542,3,63,14,214,154,748,616};

        sort(arrays);
    }

    /**
     * 获取原序列的最大位是多少
     * @param arrays 原序列
     */
    private static void sort(int[] arrays){
        //获取原序列的最大值
        int max = arrays[0];
        for(int i = 1 ; i < arrays.length ; i++){
            if(arrays[i] > max){
                max = arrays[i];
            }
        }

        //把int类型转成字符串，获取字符串的长度
        String maxStr = String.valueOf(max);
        int maxLength = maxStr.length();

        //定义二维数组，大小10，表示10个桶，每一个桶是一个数组
        int[][] bucket = new int[10][arrays.length];

        //辅助数组
        int[] bucketElementCount = new int[10];

        //遍历原序列
        for(int i = 0 ; i < arrays.length ; i++){
            //获取个位数
            int locationElement = arrays[i] % 10;

            //放入桶中
            bucket[locationElement][bucketElementCount[locationElement]] = arrays[i];
            bucketElementCount[locationElement]++;
        }

        //遍历每一个数组，将元素存放原数组中
        int index = 0;
        for(int i = 0 ; i < bucketElementCount.length ; i++){
            if(bucketElementCount[i] != 0){
                for(int j = 0 ; j < bucketElementCount[i] ; j++){
                    arrays[index++] = bucket[i][j];
                }
            }
            bucketElementCount[i] = 0;
        }

        System.out.println(Arrays.toString(arrays));

        //第一轮针对个位数进行比较
        for(int i = 0 ; i < arrays.length ; i++){
            int locationElement = arrays[i] / 1 % 10;
            bucket[locationElement][bucketElementCount[locationElement]] = arrays[i];
            bucketElementCount[locationElement]++;
        }

        //取出来按照桶的顺序放回原数组中
        int indx = 0;
        for(int i = 0 ; i < bucketElementCount.length ; i++){
            if(bucketElementCount[i] != 0){
                for(int j = 0 ; j < bucketElementCount[i] ; j++){
                    arrays[indx++] = bucket[i][j];
                }
            }
            bucketElementCount[i] = 0;
        }
    }
}
